{\magonebf 4.3 Dictionaries (dictionary)}

An instance $D$ of the data type $dictionary$ is a collection of items 
($dic\_item$). Every item in $D$ contains a key from a linearly ordered 
data type $K$, called the key type of $D$, and an information from a data 
type $I$, called the information type  of $D$. The number of items in $D$ 
is called the size of $D$. A dictionary of size zero is called the empty 
dictionary. We use $<k,i>$ to denote an item with key $k$ and information 
$i$ ($i$ is said to be the information associated with key $k$).  For each 
$k \in K$ there is at most one item $<k,i> \in D$.


\bigskip
{\bf 1. Declaration of a dictionary type}

\decltwo dictionary K I

introduces a new data type with name \name\ consisting of all 
dictionaries with key type $K$ and information type $I$.
\precond $K$ is linearly ordered.


\bigskip
{\bf 2. Creation of a dictionary}


\create D {}

creates an instance \var\ of type \name\ and initializes \var\ to the 
empty dictionary. 



\bigskip
{\bf 3. \operations}

\+\cleartabs & \hskip 1.8truecm & \hskip 6truecm &\cr
\+\op K         key {dic\_item\ it}  
                              {returns the key of item $it$.}
\+\nop                        {\precond $it$ is an item in \var.}
\smallskip
\+\op I         inf {dic\_item\ it}  
                              {returns the information of item $it$.}
\+\nop                        {\precond $it$ is an item in \var.}
\smallskip
\+\op dic\_item insert {K\ k,\ I\ i} 
                              {associates the information $i$ with the key $k$.}
\+\nop                        {If there is an item $<k,j>$ in \var\ then $j$ is}
\+\nop                        {replaced by i, else a new item $<k,i>$ is added}
\+\nop                        {to \var. In both cases the item is returned.}
\smallskip
\+\op dic\_item lookup {K\ k} 
                              {returns the item with key $k$ (nil if no such }
\+\nop                        {item exists in \var).}
\smallskip
\+\op I         access {K\ k} 
                              {returns the information associated with key $k$}
\+\nop                        {\precond there is an item with key $k$ in \var.}
\smallskip
\+\op void      del {K\ k}         
                              {deletes the item with key $k$ from \var}
\+\nop                        {(null operation, if no such item exists).}
\smallskip
\+\op void      del\_item {dic\_item\ it}   
                              {removes item $it$ from \var.}
\+\nop                        {\precond $it$ is an item in \var.}
\smallskip
\+\op void      change\_inf {dic\_item\ it,\ I\ i} 
                              {makes $i$ the information of item $it$.}
\+\nop                        {\precond $it$ is an item in \var.}
\smallskip
\+\op void      clear {}      {makes \var\ the empty dictionary.}
\smallskip 
\+\op bool      empty {}      {returns true if \var\ is empty, false otherwise.}
\smallskip 
\+\op int       size {}       {returns the size of \var.}



\bigskip
{\bf 4. Iteration}

{\bf forall\_dic\_items}($i,D$) 
$\{$ ``the items of $D$ are successively assigned to $i$ '' $\}$



\bigskip
{\bf 5. Implementation}


Dictionaries are implemented by leaf oriented red black trees.
Operations insert, lookup, del\_item, del take 
time $O(\log n)$, key, inf, empty, size, change\_inf take time $O(1)$, 
and clear takes time $O(n)$.  Here $n$ is the current size of the dictionary. 
The space requirement is $O(n)$.
 


\bigskip
{\bf 6. Example}
\smallskip
\input prog/dic.prog

